import java.util.*;
import common.TreeNode;
import static org.junit.Assert.assertArrayEquals;

/**
 * 这是 LeetCode 第 105. 根据前序遍历和中序遍历构造二叉树 的解决方案
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 */
class ConstructBinaryTreeFromPreorderAndInorderTraversal{
/**
 * 方法： buildTree
 * 逻辑: 根据给定的前序遍历和中序遍历数组构造二叉树。
 * Args:
 *   preorder (int[]): 前序遍历数组。
 *   inorder (int[]): 中序遍历数组。
 * Returns:
 *   TreeNode: 构造的二叉树的根节点。
 * Time:  
 *   O(n^2)，其中 n 是数组的长度，因为每次递归调用中查找根节点在中序遍历中的位置需要 O(n) 时间。
 * Space:  
 *   O(n)，递归调用栈的深度最多为 n。
 */
public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        // 创建根节点
        TreeNode root = new TreeNode(preorder[0]);
        // 找到根节点在中序遍历中的位置
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                rootIndex = i;
                break;
            }
        }
        // 递归构建左子树和右子树
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootIndex + 1), Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder, rootIndex + 1, preorder.length), Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length));
        return root;
    }

    int[] preOrder;
    Map<Integer, Integer> dic = new HashMap<>();

    
    /**
     * 方法： buildTree1
     * 逻辑: 根据给定的前序遍历和中序遍历数组构造二叉树。
     * Args:
     *   preorder (int[]): 前序遍历数组。
     *   inorder (int[]): 中序遍历数组。
     * Returns:
     *   TreeNode: 构造的二叉树的根节点。
     * Time:  
     *   O(n)，其中 n 是数组的长度，因为每次递归调用中查找根节点在中序遍历中的位置需要 O(n) 时间。
     * Space:  
     *   O(n)，递归调用栈的深度最多为 n。
     */
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        preOrder = preorder;
        for(int i = 0; i<inorder.length; i++){
            dic.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }

    public TreeNode recur(int root, int left, int right){
        if(left > right) return  null;
        int rootIndex = dic.get(preOrder[root]);
        TreeNode node = new TreeNode(preOrder[root]);
        node.left = recur(root + 1, left, rootIndex - 1);
        node.right = recur(rootIndex - left + root + 1, rootIndex + 1, right);
        return node;
    }


    public static void main(String[] args) {
        ConstructBinaryTreeFromPreorderAndInorderTraversal solution = new ConstructBinaryTreeFromPreorderAndInorderTraversal();
        // 调用测试方法
        solution.testBuildTree();
    }

    public void testBuildTree() {
        // 示例 1
        int[] preorder1 = {3, 9, 20, 15, 7};
        int[] inorder1 = {9, 3, 15, 20, 7};
        TreeNode result1 = buildTree(preorder1, inorder1);
        Integer[] expected1 = {3, 9, 20, null, null, 15, 7};
        assertTreeEquals(result1, expected1);
        System.out.println("Test Case 1 Passed");

        // 示例 2
        int[] preorder2 = {-1};
        int[] inorder2 = {-1};
        TreeNode result2 = buildTree(preorder2, inorder2);
        Integer[] expected2 = {-1};
        assertTreeEquals(result2, expected2);
        System.out.println("Test Case 2 Passed");

    }

    private void assertTreeEquals(TreeNode root, Integer[] expected) {
        Integer[] result = treeToArray(root);
        assertArrayEquals(expected, result);
    }

    private Integer[] treeToArray(TreeNode root) {
        if (root == null) {
            return new Integer[0]; // 返回空数组
        }

        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current != null) {
                result.add(current.val);
                queue.offer(current.left);
                queue.offer(current.right);
            } else {
                result.add(null); // 添加 null 以保持树的结构
            }
        }

        // 去掉末尾的 null 值
        while (result.size() > 0 && result.get(result.size() - 1) == null) {
            result.remove(result.size() - 1);
        }

        return result.toArray(new Integer[0]); // 转换为 Integer 数组
    }
}



